package tree.leetcode_113_medium_backtrace;

import java.util.ArrayList;
import java.util.List;

public class PathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(13);
        PathSum pathSum = new PathSum();
        pathSum.pathSum(root,13);
    }
    //方法一：深度优先遍历，复杂度很高，低效。（使用此方法可以更加深刻理解引用传递和值传递）
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        dfs(root, sum,path, res);
        return res;
    }

    /**
     *  解题思路：通过一个集合来记录所有的路径组合，如果在到叶子结点处，等于目标和，就返回所有可行的路径组合。
     *
     *  如果参数是原始数据类型（primitive data type）：在调用函数时，将实际参数通过复制的方式传入函数中。如果函数中对参数进行修改
     *  不会影响到实际参数；
     *
     *  如果参数是引用数据类型（reference data type）：在调用函数时，将实际参数的 内存地址 复制到函数中。如果函数中对参数进行修改
     *  将会影响到实际参数
     *
     * @param root  当前节点
     * @param sum   给定的路径值
     * @param path  记录每一个可行的路径的集合
     * @param res   返回可行的路径的集合 的集合
     */
    public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        /**
         * 自己想到的错误做法：在递归过程中，使用参数path的集合来记录路径组合。
         *      结果：会将所有路径结果都记录。
         path.add(root.val);
         if (root.left == null && root.right == null) {
             if (sum == root.val) {
                res.add(path);
            }
            return;
         }

         如果输入是：[5,4,8,11,null,13,4,7,2,null,null,5,1]
         使用错误方法的结果：[[5,4,11,7,2,8,13,4,5,1],[5,4,11,7,2,8,13,4,5,1]]
         **/

        /**
         *  错误方法的原因：
         *      在递归过程中，会不断改变path集合，由于是引用数据类型，会影响实际参数的改变。
         *  正确做法：
         *      每一个递归过程中，都new 一个新的集合，并将之前符合条件的集合复制到新的集合中
         *      这样new的集合既可以保存之前的结果，又可以添加新的结果。
         */

        //每一个递归过程，都要new 和 复制，导致效率很差。
        List<Integer> temp = new ArrayList<>(path);
        temp.add(root.val);
        if (root.left == null && root.right == null && sum == root.val) {
            res.add(temp);
            return;
        }
        dfs(root.left, sum - root.val, temp, res);
        dfs(root.right, sum - root.val, temp, res);
    }
}
